package com.xiyou.leetcode;

/**
 * 题目描述:
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 *
 * 示例1:
 * 输入：[7,1,5,3,6,4]
 * 输出：5
 * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
 *
 * 示例2:
 * 输入：prices = [7,6,4,3,1]
 * 输出：0
 * 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
 */
public class StockPrice1 {

    /**
     * 这是自己的第一种思路 运用了遍历判断的方式
     * 这就是一种暴力法的解决 时间复杂度过高 没有通过
     *
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        // 用来存储利润
        int maxProfits = 0;
        // 数组的长度是多少 表示的是就是有多少天的股票金额
        // 我们需要从头开始
        for (int i = 0; i < prices.length; i++) {
            int buyPrice = prices[i];
            for (int j = i + 1; j < prices.length; j++) {
                // 如果买入的价格小于当前的价格
                // 并且当前的最大利润 < 现在计算的利润
                if (buyPrice < prices[j] && maxProfits < prices[j] - prices[i]) {
                    maxProfits = prices[j] - prices[i];
                }
            }
        }
        return maxProfits;
    }

    /**
     * 这是第二种思路 利用动态规划的思想
     * 其状态转移方程参考上面的笔记
     *
     * @param prices 数组，第i天的的股票价格是prices[i]
     * @return
     */
    public int maxProfit2(int[] prices) {

        // 如果数组的长度是0，那么我们直接就返回最大的利润是0
        if (prices == null || prices.length == 0) {
            return 0;
        }

        // 定义一个数组用来存储第i天剩下1股 和 第i天剩下0股的情况
        int[][] db = new int[prices.length][2];
        // 第0天剩下0股的利润肯定是0
        db[0][0] = 0;
        // 第0天剩下1股的情况，利润是-prices[0] 这个我们在上面的笔记中已经推算了
        db[0][1] = -prices[0];

        // 循环遍历数组 因为我们最大的利润肯定是最后一天持有0股的情况
        // 我们循环遍历从第二天开始，即下标从1开始，因为下标是0表示第一天的我们作为界限值，已经推算出来了
        for (int i = 1; i < prices.length; i++) {
            // 套用我们的状态转移方程，我们的状态转移方程已经在上面的笔记中推算了，这里直接套用那两个方程就行
            // 第i天持有0股的最大利润
            db[i][0] = Math.max(db[i - 1][0], db[i - 1][1] + prices[i]);
            // 第i天持有1股的最大利润
            db[i][1] = Math.max(db[i - 1][1], -prices[i]);
        }

        // 最大的利润肯定是最后一天持有0股的情况
        return db[prices.length - 1][0];
    }

    public static void main(String[] args) {
        int[] prices = {7,6,4,3,1};
        int maxPrice = new StockPrice1().maxProfit2(prices);
        System.out.println(maxPrice);
    }
}
